import java.util.*;

/**
 * 297. 二叉树的序列化与反序列化
 * https://leetcode-cn.com/problems/serialize-and-deserialize-binary-tree/
 */
public class Solutions_297 {
    public static void main(String[] args) {
//        String rootStr = "[1,2,3,#,#,4,5]";
//        String rootStr = "[1,2,3,#,4,6]";
        String rootStr = "[]";

        Codec obj = new Codec();
        // 字符串反序列化为二叉树
        TreeNode resRoot = obj.deserialize(rootStr);
        // 二叉树序列化为字符串
        System.out.println(obj.serialize(resRoot));
    }
}

/**
 * BFS 实现
 */
class Codec {

    /**
     * 序列化：TreeNode -> String
     */
    public String serialize(TreeNode root) {
        if (root == null) {
            return "[]";
        }
        StringBuilder sb = new StringBuilder();
        sb.append("[");
        Queue<TreeNode> queue = new LinkedList<>();
        queue.add(root);
        while (!queue.isEmpty()) {
            TreeNode node = queue.poll();
            if (node == null) {
                sb.append("#,");
                continue;
            }
            sb.append(node.val + ",");
            queue.add(node.left);
            queue.add(node.right);
        }
        // 去除字符串尾部的逗号
        sb.setCharAt(sb.length() - 1, ']');
        return sb.toString();
    }

    /**
     * 反序列化：String -> TreeNode
     */
    public TreeNode deserialize(String data) {
        if (data.length() < 1) {
            return null;
        }
        // 去前后的两个括号
        data = data.substring(1, data.length() - 1);
        if (data.length() < 1) {
            return null;
        }
        // 队列记录树节点
        Queue<TreeNode> queue = new LinkedList<>();
        // 根据逗号分隔
        String[] nodes = data.split(",");
        // 创建父节点并入队
        TreeNode root = new TreeNode(Integer.valueOf(nodes[0]));
        queue.add(root);

        for (int i = 1; i < nodes.length; i++) {
            TreeNode curNode = queue.poll();
            // 关键：后面跟着的两个元素，就是其 parentNode 的左右子节点
            if (!"#".equals(nodes[i])) {
                // parentNode 的左子节点不为空，创建节点，并将节点入队
                curNode.left = new TreeNode(Integer.valueOf(nodes[i]));
                queue.add(curNode.left);
            }
            if (i < nodes.length - 1 && !"#".equals(nodes[++i])) {
                // parentNode 的右子节点不为空，创建节点，并将节点入队
                curNode.right = new TreeNode(Integer.valueOf(nodes[i]));
                queue.add(curNode.right);
            }
        }
        return root;
    }
}
